#include <vector>
#include <cstring>

using namespace std;

// 参加会议的最多员工数
// 一个公司准备组织一场会议，邀请名单上有 n 位员工
// 公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工
// 员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工
// 每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议
// 每位员工喜欢的员工 不会 是他自己。给你一个下标从 0 开始的整数数组 favorite
// 其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目
// 测试链接 : https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/
// 本题考察的是内向基环树，有关内向基环树的介绍可以看一下下面的帖子
// 帖子链接：https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/solutions/1187830/nei-xiang-ji-huan-shu-tuo-bu-pai-xu-fen-c1i1b/

// 数组实现的队列
class Solution 
{
public:
    int maximumInvitations(vector<int>& favorite) 
    {
        // 图 : favorite[a] = b : a -> b
        int n = favorite.size();
        vector<int> indegree(n);
        for(int y : favorite)
        {
            ++indegree[y];
        }

        int q[n], l = 0, r = 0;
        memset(q, 0, sizeof(q));
        for(int i = 0; i < n; ++i)
        {
            if(!indegree[i]) q[r++] = i;
        }        

        // depth[i]：不包括 i 在内，i 之前的最长链的长度
        vector<int> depth(n);
        while(l < r)
        {
            int x = q[l++];
            int y = favorite[x];
            depth[y] = max(depth[y], depth[x] + 1);
            if(--indegree[y] == 0) q[r++] = y;
        }

        // 此时 indegree[i] 大于 0，则说明 i 在环内
        // 目前图中的点，不在环上的点，都删除了！ indegree[i] == 0
		// 可能性 1 : 所有小环(中心个数 == 2)，算上中心点 + 延伸点，总个数
        // 可能性 2 : 所有大环(中心个数 > 2)，只算中心点，最大环的中心点个数
        int sumOfSmallRings = 0, bigRings = 0;
        for(int i = 0; i < n; ++i)
        {
            // 只关心的环！
            if(indegree[i] > 0)
            {
                int ringSize = 1;
                indegree[i] = 0; // 标记该基环已经访问过了，避免重复访问相同的基环
                for(int j = favorite[i]; j != i; j = favorite[j])
                {
                    ++ringSize;
                    indegree[j] = 0;
                }
                if(ringSize == 2) sumOfSmallRings += depth[i] + depth[favorite[i]] + 2;
                else bigRings = max(bigRings, ringSize);
            }
        }
        return max(sumOfSmallRings, bigRings);
    }
};

// 使用语言标准库的队列
class Solution 
{
public:
    int maximumInvitations(vector<int>& favorite) 
    {
        // 图 : favorite[a] = b : a -> b
        int n = favorite.size();
        vector<int> indegree(n);
        for(int y : favorite)
        {
            ++indegree[y];
        }

        queue<int> q;
        for(int i = 0; i < n; ++i)
        {
            if(!indegree[i]) q.push(i);
        }        

        // depth[i]：不包括 i 在内，i 之前的最长链的长度
        vector<int> depth(n);
        while(!q.empty())
        {
            int x = q.front();
            q.pop();
            int y = favorite[x];
            depth[y] = max(depth[y], depth[x] + 1);
            if(--indegree[y] == 0) q.push(y);
        }

        // 此时 indegree[i] 大于 0，则说明 i 在环内
        // 目前图中的点，不在环上的点，都删除了！ indegree[i] == 0
		// 可能性 1 : 所有小环(中心个数 == 2)，算上中心点 + 延伸点，总个数
        // 可能性 2 : 所有大环(中心个数 > 2)，只算中心点，最大环的中心点个数
        int sumOfSmallRings = 0, bigRings = 0;
        for(int i = 0; i < n; ++i)
        {
            // 只关心的环！
            if(indegree[i] > 0)
            {
                int ringSize = 1;
                indegree[i] = 0; // 标记该基环已经访问过了，避免重复访问相同的基环
                for(int j = favorite[i]; j != i; j = favorite[j])
                {
                    ++ringSize;
                    indegree[j] = 0;
                }
                if(ringSize == 2) sumOfSmallRings += depth[i] + depth[favorite[i]] + 2;
                else bigRings = max(bigRings, ringSize);
            }
        }
        return max(sumOfSmallRings, bigRings);
    }
};